#define DEBUG
#include <cstdio>
#define MAXN 50000
#define MAXLOGN 16

using namespace std;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

class Tree {
public:
  int dep[MAXN+1], f[MAXN+1][MAXLOGN+1];

  void update(int o, int fa) {
    if (fa==0) {
      dep[o] = o==1 ? dep[fa]+1 : 0;
    } else {
      dep[o] = dep[fa]+1;
    }

    f[o][0] = fa;
    for (int i=1; i<=MAXLOGN; i++) {
      f[o][i] = f[f[o][i-1]][i-1];
    }
  }

  int lca(int u, int v) {
    if (dep[u]<dep[v]) {
      int temp=u;
      u=v, v=temp;
    }
    for (int i=MAXLOGN; i>=0; i--) {
      if (dep[f[u][i]]>=dep[v]) {
	u = f[u][i];
      }
    }
    if (u==v) {
      return u;
    }
    for (int i=MAXLOGN; i>=0; i--) {
      if (f[u][i]!=f[v][i]) {
	u=f[u][i], v=f[v][i];
      }
    }
    return f[u][0];
  }
};

class SegmentTree {
public:
  Tree tree;
  int mark[4*MAXN+1];
  
  void set(int o, int l, int r, int tl, int tr, int tv) {
    if (l==tl && r==tr) {
      if (mark[o]) {
	mark[o] = tree.lca(mark[o], tv);
      } else {
	mark[o] = tv;
      }
    } else {
      int mid=(l+r)/2;
      if (tl<=mid && tr>=l) {
	set(o*2, l, mid, max(tl, l), min(tr, mid), tv);
      }
      if (tl<=r && tr>mid) {
	set(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r), tv);
      }
    }
  }

  int get(int o, int l, int r, int t) {
    if (l==r) {
      return mark[o];
    } else {
      int mid=(l+r)/2, x;
      if (t<=mid) {
	x=get(o*2, l, mid, t);
      } else {
	x=get(o*2+1, mid+1, r, t);
      }
      if (!mark[o]) {
	return x;
      } else if (!x) {
	return mark[o];
      } else {
	return tree.lca(mark[o], x);
      }
    }
  }
};

int main() {
#ifdef DEBUG
  freopen("4240.in", "r", stdin);
  freopen("4240.out", "w", stdout);
#endif

  static int a[MAXN+1], l[MAXN+1], r[MAXN+1];
  int n;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) {
    scanf("%d", a+i);
  }
  for (int i=1; i<=n; i++) {
    scanf("%d %d", l+i, r+i);
  }
  
  static SegmentTree sgt;
  for (int i=1; i<=n; i++) {
    int fa=sgt.get(1, 1, n, a[i]);
    sgt.tree.update(i, fa);
    if (sgt.tree.dep[i]>0) {
      sgt.set(1, 1, n, l[i], r[i], i);
    }
  }
  
  for (int i=1; i<=n; i++) {
    if (sgt.tree.dep[i]) {
      printf("%d\n", sgt.tree.dep[i]);
    } else {
      printf("-1\n");
    }
  }

  fcloseall();
  return 0;
}
